package demo12_binarysorttree;

public class BinarySortTree {
    Node root;

    /**
     * 向二叉排序树中插入节点
     *
     * @param parent 父节点
     * @param node
     */
    public void add(Node parent, Node node) {
        //如果是一颗空树
        if (this.root == null) {
            this.root = node;
        } else {
            //判断传入的节点的值比当前子树的根节点的值大还是小
            if (node.value < parent.value) {
                //如果左节点为空
                if (parent.left == null) {
                    parent.left = node;
                    //如果不为空
                } else {
                    add(parent.left, node);
                }
            } else {
                if (parent.right == null) {
                    parent.right = node;
                    //如果不为空
                } else {
                    add(parent.right, node);
                }
            }
            //查询是否平衡
            //进行右旋转   左边长 右边短
            if (height(parent.left) - height(parent.right) >= 2) {
                //双旋转
                if (parent.left.left != null && height(parent.left.left) > height(parent.right.right))
                    leftRotete(parent.left);
                rightRotete(parent);
            } else if (height(parent.left) - height(parent.right) <= -2) {
                if (parent.right.right != null && height(parent.right.right) > height(parent.left.left))
                    rightRotete(parent.right);
                leftRotete(parent);
            }
        }
    }

    public void add(Node node) {
        add(root, node);
    }

    /**
     * 右旋转
     *
     * @param parent
     */
    private void rightRotete(Node parent) {
        Node newNode = new Node(parent.value);
        //把新节点的右子树设置为当前节点的左子树的右子树
        newNode.left = parent.left.right;
        //把新节点的右子树设置为当前节点的右子树
        newNode.right = parent.right;
        //把当前节点的值换为左子节点的值  为了保持树的根地址不变
        parent.value = parent.left.value;
        //把当前节点的左子树设置为左子树的左子树
        parent.left = parent.left.left;
        //把当前节点的右子树设置为新节点
        parent.right = newNode;
    }

    /**
     * 左旋转
     *
     * @param parent
     */
    private void leftRotete(Node parent) {
        Node newNode = new Node(parent.value);
        newNode.right = parent.right.left;
        newNode.left = parent.left;
        parent.value = parent.right.value;
        parent.right = parent.right.right;
        parent.left = newNode;
    }

    public int height(Node node) {
        if (node == null)
            return 0;
        return Math.max(node.left == null ? 0 : height(node.left), node.right == null ? 0 : height(node.right)) + 1;
    }

    /**
     * 中序遍历
     */
    public void midShow(Node node) {
        if (node == null) {
            return;
        }
        midShow(node.left);
        System.out.println(node.value);
        midShow(node.right);
    }

    /**
     * 节点的查找
     *
     * @param value
     * @return
     */
    public Node search(Node node, int value) {
        if (root == null) {
            return null;
        } else {
            if (node.value == value) {
                return node;
            } else if (value < node.value) {
                if (node.left == null) {
                    return null;
                }
                return search(node.left, value);
            } else {
                if (node.right == null) {
                    return null;
                }
                return search(node.right, value);
            }
        }
    }

    public Node search(int value) {
        return search(root, value);
    }

    /**
     * 删除节点
     *
     * @param value
     */
    public void delete(int value) {
        if (root == null) {
            return;
        } else {
            //找到这个节点
            Node target = search(value);
            if (target == null) {
                return;
            }
            //找到他的父节点
            Node parent = searchParent(value);
            //要删除的节点是叶子节点
            if (target.left == null && target.right == null) {
                //要删除的节点是父节点的左子节点
                if (parent.left.value == value) {
                    parent.left = null;
                    //要删除的节点是父节点的右子节点
                } else {
                    parent.right = null;
                }
                //要删除的节点有两个子节点的情况
            } else if (target.left != null && target.right != null) {
                //删除右子树中值最小的节点，取获取到该节点的值
                int min = deleteMin(target.right);
                //替换目标节点中的值
                target.value = min;
            }
            //要删除的节点有一个个子节点的情况
            else {
                //有左子节点
                if (target.left != null) {
                    //要删除的节点是父节点的左子节点
                    if (parent.left.value == value) {
                        parent.left = target.left;
                        //要删除的节点是父节点的右子节点
                    } else {
                        parent.right = target.left;
                    }
                    //有右子节点
                } else {
                    if (parent.left.value == value) {
                        parent.left = target.right;
                        //要删除的节点是父节点的右子节点
                    } else {
                        parent.right = target.right;
                    }
                }

            }
        }
    }

    /**
     * 删除一棵树中最小的节点
     *
     * @param node
     * @return
     */
    private int deleteMin(Node node) {
        Node target = node;
        //递归向左找最小
        while (node.left != null) {
            target = target.left;
        }
        //删除最小的这个节点
        delete(target.value);
        return target.value;
    }

    /**
     * 搜索父节点
     *
     * @param value
     * @return
     */
    public Node searchParent(Node node, int value) {
        if (root == null) {
            return null;
        } else {
            if ((node.left != null && node.left.value == value) || (node.right != null && node.right.value == value)) {
                return node;
            } else {
                if (node.value > value) {
                    return searchParent(node.left, value);
                } else if (node.value < value && node.right != null) {
                    return searchParent(node.right, value);
                }
                return null;
            }
        }
    }

    public Node searchParent(int value) {
        return searchParent(root, value);
    }
}
